package org.nowcoder.leetcode.DP;

import java.util.Arrays;

/**
 * Title  : 1049. Last Stone Weight II
 * Source : https://leetcode.cn/problems/last-stone-weight-ii/description/
 * Author : XrazYang
 * Date   : 2023-1-19
 */

public class LeetCode_1049 {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        //特殊情况
        if (n == 1) return stones[0];
        int sum = Arrays.stream(stones).sum();
        int m = sum / 2; //背包容量
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[m] - dp[m];
    }
}
